package com.example;

import java.util.Stack;

/**
 * @Author loubobooo
 * @Description #32. 最长有效括号
 * @Date 2022/3/29
 */
public class LongestValidParentheses {

    /**
     * @Author loubobooo
     * @Description 给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。
     * @Date 2022/3/29
     * @Param
     * @return
     **/
    public int longestValidParentheses(String s) {
        if(s == null || s.isEmpty()){
            return 0;
        }
        // 我们首先将 -1放入栈顶。
        //对于遇到的每个``'('`` ，我们将它的下标放入栈中。
        //对于遇到的每个``')'`` ，我们先弹出栈中元素，再将当前元素的下标元素和栈顶元素做差，得出当前有效括号字符串的长度。
        // 通过这种方法，我们继续计算有效子字符串的长度，并最终返回最长有效子字符串的长度
        int result = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        char[] chars = s.toCharArray();
        for (int i = 0, length = chars.length; i < length; i++) {
            if(chars[i] == '('){
                stack.push(i);
            }else{
                stack.pop();
                if(stack.isEmpty()){
                    stack.push(i);
                }
                Integer peek = stack.peek();
                int temp = i - peek;
                result = Math.max(result, temp);
            }
        }
        return result;
    }

    public int longestValidParentheses2(String s) {
        if(s == null || s.isEmpty()){
            return 0;
        }
        // 用栈模拟一遍 记录下标，将所有无法匹配的括号的位置全部置1
        //例如: "()(()"的mark为[0, 0, 1, 0, 0]
        //再例如: ")()((())"的mark为[1, 0, 0, 1, 0, 0, 0, 0]
        //经过这样的处理后, 此题就变成了寻找最长的连续的0的长度
        int[] arr = new int[s.length()];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            if(s.charAt(i) == '('){
                stack.push(i);
            }else{
                if(stack.isEmpty()){
                    arr[i] = 1;
                }else{
                    stack.pop();
                }
            }
        }
        while(!stack.isEmpty()){
            arr[stack.pop()] = 1;
        }
        int result = 0;
        int temp = 0;
        for (int i = 0; i < arr.length; i++) {
            if(arr[i] == 1){
                temp = 0;
            }else{
                temp++;
                result = Math.max(result, temp);
            }
        }

        return result;
    }


}
